An important consideration in the design and utilization of multiprocessor computers is resource management. That is, in addition to the management of conventional resources such as memory and processor time, it is necessary to manage other resources such as processing elements, or processors, and their communication links.
A specific consideration of this resource management is an ability to efficiently allocate and deallocate processors in consecutive computing tasks. Typically, in large computing applications, multiple computing tasks are executed on a single multiprocessor computer, where each task is comprised of a number of concurrently executable (within precedence constraints) sub-tasks. These sub-tasks generally arise at indeterminate times with varying computational requirements, and each task thereof may not require the use of all processors within the computer. Additionally, in large computing applications, it may be desirable to share the computer across multiple tasks in the manner of prior art timesharing systems.
Therefore, in these situations, it is desirable, and often necessary, to allocate partitions of the computer to each task. A partition, as is well-known in the art, is comprised of a selected group of interconnected processors. The allocation of partitions, disadvantageously, results in the fragmentation of previously linked or paired processors over a period of time which in turn can prevent the execution of tasks requiring a certain number of processors. Thus, an allocation goal is to minimize processor group fragmentation, thereby minimizing the number of requests for processors that are unsatisfied.
In the prior art, various methods have been developed for the allocation and deallocation of processors in the performance of computational tasks. One such method is known as the "buddy system," as disclosed by Donald E. Knuth in Fundamental Algorithms, chapter 2.5 (Addison-Wesley 1973). The buddy system, however, fails in some instances to efficiently allocate processors. Consequently, additional computer running time may be required in such situations using the buddy system to perform a particular computing task.